// Copyright 2014 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef MEDIA_CAST_NET_PACING_PACED_SENDER_H_
#define MEDIA_CAST_NET_PACING_PACED_SENDER_H_

#include <stddef.h>
#include <stdint.h>

#include <map>
#include <memory>
#include <tuple>
#include <vector>

#include "base/macros.h"
#include "base/memory/weak_ptr.h"
#include "base/single_thread_task_runner.h"
#include "base/threading/non_thread_safe.h"
#include "base/time/default_tick_clock.h"
#include "base/time/tick_clock.h"
#include "base/time/time.h"
#include "media/cast/logging/logging_defines.h"
#include "media/cast/net/cast_transport_config.h"

namespace media {
namespace cast {

    // Meant to use as defaults for pacer construction.
    static const size_t kTargetBurstSize = 10;
    static const size_t kMaxBurstSize = 20;

    // The PacketKey is designed to meet two criteria:
    // 1. When we re-send the same packet again, we can use the packet key
    //    to identify it so that we can de-duplicate packets in the queue.
    // 2. The sort order of the PacketKey determines the order that packets
    //    are sent out.
    // 3. The PacketKey is unique for each RTP (frame) packet.
    struct PacketKey {
        base::TimeTicks capture_time;
        uint32_t ssrc;
        FrameId frame_id;
        uint16_t packet_id;

        PacketKey(); // Do not use.  This is for STL containers.
        PacketKey(base::TimeTicks capture_time,
            uint32_t ssrc,
            FrameId frame_id,
            uint16_t packet_id);
        PacketKey(const PacketKey& other);

        ~PacketKey();

        bool operator==(const PacketKey& key) const
        {
            return std::tie(capture_time, ssrc, frame_id, packet_id) == std::tie(key.capture_time, key.ssrc, key.frame_id, key.packet_id);
        }

        bool operator<(const PacketKey& key) const
        {
            return std::tie(capture_time, ssrc, frame_id, packet_id) < std::tie(key.capture_time, key.ssrc, key.frame_id, key.packet_id);
        }
    };

    typedef std::vector<std::pair<PacketKey, PacketRef>> SendPacketVector;

    // Information used to deduplicate retransmission packets.
    // There are two criteria for deduplication.
    //
    // 1. Using another muxed stream.
    //    Suppose there are multiple streams muxed and sent via the same
    //    socket. When there is a retransmission request for packet X, we
    //    will reject the retransmission if there is a packet sent from
    //    another stream just before X but not acked. Typically audio stream
    //    is used for this purpose. |last_byte_acked_for_audio| provides this
    //    information.
    //
    // 2. Using a time interval.
    //    Time between sending the same packet must be greater than
    //    |resend_interval|.
    struct DedupInfo {
        DedupInfo();
        base::TimeDelta resend_interval;
        int64_t last_byte_acked_for_audio;
    };

    // We have this pure virtual class to enable mocking.
    class PacedPacketSender {
    public:
        virtual bool SendPackets(const SendPacketVector& packets) = 0;
        virtual bool ResendPackets(const SendPacketVector& packets,
            const DedupInfo& dedup_info)
            = 0;
        virtual bool SendRtcpPacket(uint32_t ssrc, PacketRef packet) = 0;
        virtual void CancelSendingPacket(const PacketKey& packet_key) = 0;

        virtual ~PacedPacketSender() { }
    };

    class PacedSender : public PacedPacketSender,
                        public base::NonThreadSafe,
                        public base::SupportsWeakPtr<PacedSender> {
    public:
        // |recent_packet_events| is an externally-owned vector where PacedSender will
        // add PacketEvents related to sending, retransmission, and rejection.  The
        // |external_transport| should only be used by the Cast receiver and for
        // testing.
        PacedSender(
            size_t target_burst_size, // Should normally be kTargetBurstSize.
            size_t max_burst_size, // Should normally be kMaxBurstSize.
            base::TickClock* clock,
            std::vector<PacketEvent>* recent_packet_events,
            PacketTransport* external_transport,
            const scoped_refptr<base::SingleThreadTaskRunner>& transport_task_runner);

        ~PacedSender() final;

        // These must be called before non-RTCP packets are sent.
        void RegisterSsrc(uint32_t ssrc, bool is_audio);

        // Register SSRC that has a higher priority for sending. Multiple SSRCs can
        // be registered.
        // Note that it is not expected to register many SSRCs with this method.
        // Because IsHigherPriority() is determined in linear time.
        void RegisterPrioritySsrc(uint32_t ssrc);

        // Returns the total number of bytes sent to the socket when the specified
        // packet was just sent.
        // Returns 0 if the packet cannot be found or not yet sent.
        // This function is currently only used by unittests.
        int64_t GetLastByteSentForPacket(const PacketKey& packet_key);

        // Returns the total number of bytes sent to the socket when the last payload
        // identified by SSRC is just sent. Returns 0 for an unknown ssrc.
        // This function is currently only used by unittests.
        int64_t GetLastByteSentForSsrc(uint32_t ssrc);

        // PacedPacketSender implementation.
        bool SendPackets(const SendPacketVector& packets) final;
        bool ResendPackets(const SendPacketVector& packets,
            const DedupInfo& dedup_info) final;
        bool SendRtcpPacket(uint32_t ssrc, PacketRef packet) final;
        void CancelSendingPacket(const PacketKey& packet_key) final;

        void SetTargetBurstSize(int burst_size)
        {
            target_burst_size_ = current_max_burst_size_ = next_max_burst_size_ = next_next_max_burst_size_ = burst_size;
        }

        void SetMaxBurstSize(int burst_size) { max_burst_size_ = burst_size; }

    private:
        // Actually sends the packets to the transport.
        void SendStoredPackets();

        // Convenience method for building a PacketEvent and storing it in the
        // externally-owned container of |recent_packet_events_|.
        void LogPacketEvent(const Packet& packet, CastLoggingEvent event);

        // Returns true if retransmission for packet indexed by |packet_key| is
        // accepted. |dedup_info| contains information to help deduplicate
        // retransmission. |now| is the current time to save on fetching it from the
        // clock multiple times.
        bool ShouldResend(const PacketKey& packet_key,
            const DedupInfo& dedup_info,
            const base::TimeTicks& now);

        enum PacketType {
            PacketType_RTCP,
            PacketType_Resend,
            PacketType_Normal
        };
        enum State {
            // In an unblocked state, we can send more packets.
            // We have to check the current time against |burst_end_| to see if we are
            // appending to the current burst or if we can start a new one.
            State_Unblocked,
            // In this state, we are waiting for a callback from the udp transport.
            // This happens when the OS-level buffer is full. Once we receive the
            // callback, we go to State_Unblocked and see if we can write more packets
            // to the current burst. (Or the next burst if enough time has passed.)
            State_TransportBlocked,
            // Once we've written enough packets for a time slice, we go into this
            // state and PostDelayTask a call to ourselves to wake up when we can
            // send more data.
            State_BurstFull
        };

        bool empty() const;
        size_t size() const;

        // Returns the next packet to send. RTCP packets have highest priority, then
        // high-priority RTP packets, then normal-priority RTP packets.  Packets
        // within a frame are selected based on fairness to ensure all have an equal
        // chance of being sent.  Therefore, it is up to client code to ensure that
        // packets acknowledged in NACK messages are removed from PacedSender (see
        // CancelSendingPacket()), to avoid wasteful retransmission.
        PacketRef PopNextPacket(PacketType* packet_type,
            PacketKey* packet_key);

        // Returns true if the packet should have a higher priority.
        bool IsHighPriority(const PacketKey& packet_key) const;

        // These are externally-owned objects injected via the constructor.
        base::TickClock* const clock_;
        std::vector<PacketEvent>* const recent_packet_events_;
        PacketTransport* const transport_;

        scoped_refptr<base::SingleThreadTaskRunner> transport_task_runner_;

        // Set of SSRCs that have higher priority. This is a vector instead of a
        // set because there's only very few in it (most likely 1).
        std::vector<uint32_t> priority_ssrcs_;
        typedef std::map<PacketKey, std::pair<PacketType, PacketRef>> PacketList;
        PacketList packet_list_;
        PacketList priority_packet_list_;

        struct PacketSendRecord;
        using PacketSendHistory = std::map<PacketKey, PacketSendRecord>;
        PacketSendHistory send_history_;
        PacketSendHistory send_history_buffer_;

        struct RtpSession;
        using SessionMap = std::map<uint32_t, RtpSession>;
        // Records all the cast sessions with the sender SSRC as the key. These
        // sessions are in sync with those in CastTransportImpl.
        SessionMap sessions_;

        // Records the last byte sent for audio payload.
        int64_t last_byte_sent_for_audio_;

        size_t target_burst_size_;
        size_t max_burst_size_;

        // Maximum burst size for the next three bursts.
        size_t current_max_burst_size_;
        size_t next_max_burst_size_;
        size_t next_next_max_burst_size_;
        // Number of packets already sent in the current burst.
        size_t current_burst_size_;
        // This is when the current burst ends.
        base::TimeTicks burst_end_;

        State state_;

        bool has_reached_upper_bound_once_;

        // NOTE: Weak pointers must be invalidated before all other member variables.
        base::WeakPtrFactory<PacedSender> weak_factory_;

        DISALLOW_COPY_AND_ASSIGN(PacedSender);
    };

} // namespace cast
} // namespace media

#endif // MEDIA_CAST_NET_PACING_PACED_SENDER_H_
